package com.leetcode;

/**
 * [
 * [1,   4,  7, 11, 15],
 * [2,   5,  8, 12, 19],
 * [3,   6,  9, 16, 22],
 * [10, 13, 14, 17, 24],
 * [18, 21, 23, 26, 30]
 * ]
 * <p>
 * 从n*m矩阵查找元素
 * n方向，从左到右，依次递增
 * m方向，从上到下，依次递增
 * <p>
 * 考察点：二分法
 */
public class Offer04 {

    public static void main(String[] args) {
        int[][] nums = {
                {1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        };
        System.out.println(String.format("查找元素%d = %b", 13, findTarget(nums, 13)));
        System.out.println(String.format("查找元素%d = %b", 20, findTarget(nums, 20)));
        System.out.println(String.format("查找元素%d = %b", 30, findTarget(nums, 30)));
        System.out.println(String.format("查找元素%d = %b", 56, findTarget(nums, 56)));
    }


    /**
     * 查找target是否在nums内
     * 找到      返回true
     * 没找到     返回false
     *
     * @param nums   目标数组
     * @param target 目标元素
     * @return
     */
    public static boolean findTarget(int[][] nums, int target) {
        // TODO 行数
        int ilen = nums.length;
        int i = 0;
        int j = nums[0].length - 1;

        // TODO 从右上角开始遍历
        while (i < ilen && j >= 0) {
            // TODO 如果目标值小，往数值大的方向找
            if (nums[i][j] < target) {
                i++;
            }
            // TODO 如果比目标值大，往数值小的方向找
            else if (nums[i][j] > target) {
                j--;
            } else if (nums[i][j] == target) {
                return true;
            }
        }

        // TODO 找到最后都没找到
        return false;
    }
}
